Computational Game Theory

\[ \newcommand{\IR}{\mathbb{R}} \newcommand{\IRnn}{\IR_{\geq 0}} \newcommand{\IRp}{\IR_{\gt 0}} \newcommand{\IN}{\mathbb{N}} \newcommand{\INo}{\IN_0} \newcommand{\INs}{\IN^\ast} \newcommand{\coloneqq}{\mathbin{:=}} \newcommand{\eqqcolon}{\mathbin{=:}} \newcommand{\coloniff}{\mathbin{:\!\!\iff}} \newcommand{\dcup}{\mathbin{\dot\cup}} \newcommand{\sMid}{\,|\,} \newcommand{\Set}[1]{\left\lbrace#1\right\rbrace} \newcommand{\SMid}{\,\middle|\,} \newcommand{\abs}[1]{\lvert#1\rvert} \newcommand{\Abs}[1]{\left\lvert#1\right\rvert} \newcommand{\norm}[1]{\lVert#1\rVert} \newcommand{\Norm}[1]{\left\lVert#1\right\rVert} \newcommand{\PSet}[1]{2^{#1}} \newcommand{\transp}{^\top} \newcommand{\eps}{\varepsilon} \]

§4 Congestion Games

finite set of players $N$
finite set of resources $R$
sets of strategies $S_i \subseteq \IR^R$
$\ell: S \to \IR^R, s \mapsto \ell(s) \coloneqq \sum_{i \in N}s_i$ load/congestion vector
player specific, load-dependent, per-unit resource costs $c_i: \IR^R \to \IR^R$
players' cost functions $\pi_i: S \to \IR, s \mapsto s_i\transp c_i(\ell(s)) = \sum_{r \in R}s_{i,r}c_{i,r}(\ell(s))$

⤳ generic congestion game $(N,S,\pi)$ (cost minimization game!)

unweighted congestion game	$\coloniff S_i \subseteq \set{0,1}^R$
weighted congestion game	$\coloniff S_i \subseteq \set{0,d_i}^R$
player-independent/homogeneous costs	$\coloniff \forall i,j \in N: c_i = c_j$
separable costs	$\coloniff \ell_r(s) = \ell_r(s') \implies c_{i,r}(\ell(s)) = c_{i,r}(\ell(s'))$


	$(5,5)$	$(4,5)$
	$(5,4)$	$(7,7)$

$D=(V,E)$

$R=E$

§4.2 Unweighted Congestion Games

Here: Only unweighted congestion games (with separable, homog. cost functions)
⤳ have resource cost functions $c_r: \INo \to \IR$ and
⤳ set of resources used by player $i$ (under $s_i$) $R(s_i) \coloneqq \set{r \in R \sMid s_{i,r} = 1}$
⤳ $\pi_i(s) = \sum_{r \in R(s_i)}c_r(\ell_r(s)) = \sum_{r \in R(s_i)}c_r(\abs{\set{j \in N \sMid r \in R(s_j)}})$

Thm. 4.5: Every unweighted congestion game has a pure NE.

Thm. 4.5: Every unweighted congestion game is exact potential game.

Rosenthal potential $P(s) \coloneqq \sum_{r \in R}\sum_{k=1}^{\ell_r(s)}c_r(k)$

Thm. 4.13: Every exact potential game is isomorphic to unweighted congestion game.

games $G=(N,S,u)$, $H=(N,T,v)$ are isomorphic if $\exists \phi_i: S_i \to T_i$ bijections s.th. $\forall i \in N, s \in S: u_i(s) = v_i(\phi_1(s_1), \dots, \phi_n(s_n))$.

Thm. 3.10: $G$ has exact potential iff $\exists G^C=(N,S,u^C), G^D=(N,S,u^D)$ s.th. $G=G^C+G^D$, i.e., $u_i = u^C_i + u^D_i$, and

$G^C$ coordination game, i.e., $u^C_i = u_j^C$
$G^D$ dummy game, i.e., $u^D(.,s_{-i}) = \mathrm{const.}$

Lem. 4.8: Every coordination game is isomorphic to unweighted congestion game

Lem. 4.10: Every dummy game is isomorphic to unweighted congestion game

coord. game $G=(N,S,u)$ $\mapsto$ cong. game $H=(N,T,\pi)$:

$R \coloneqq S$
$R(T_i) \coloneqq \Set{\bigcup_{s_{-i} \in S_i}\set{(s_i,s_{-i})} \SMid s_i \in S_i}$
$c_s(k) \coloneqq \begin{cases}u_i(s) \text{ for any } i \in N, &\text{if } k = n\\0, &\text{else}\end{cases}$

dummy. game $G=(N,S,u)$ $\mapsto$ cong. game $H=(N,T,\pi)$:

$R \coloneqq \bigcup_{i \in N}S_{-i}$
$R(T_i) \coloneqq \Set{S_{-i} \cup \bigcup_{j \neq i}\set{s'_{-j} \in S_{-j} \sMid s_i' \neq s_i} \SMid s_i \in S_i}$
$c_{s_{-i}}(k) \coloneqq \begin{cases}u_i(s_i,s_{-i}) \text{ for any } s_i \in S_i, &\text{if } k = 1\\0, &\text{else}\end{cases}$

	L	C	R
T	$(0,0)$	$(1,1)$	$(2,2)$
B	$(2,2)$	$(3,3)$	$(4,4)$

	L	C	R
T	$(0,2)$	$(1,2)$	$(3,2)$
B	$(0,3)$	$(1,3)$	$(3,3)$

	L	C	R
T	$(0+0,0+2)$	$(1+1,1+2)$	$(2+3,2+2)$
B	$(2+0,2+3)$	$(3+1,3+3)$	$(4+3,4+3)$